{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Process Tasks Using Servers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: assignTasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用服务器处理任务"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>下标从 0 开始</strong> 的整数数组 <code>servers</code> 和 <code>tasks</code> ，长度分别为 <code>n</code>​​​​​​ 和 <code>m</code>​​​​​​ 。<code>servers[i]</code> 是第 <code>i<sup>​​​​​​</sup></code>​​​​ 台服务器的 <strong>权重</strong> ，而 <code>tasks[j]</code> 是处理第 <code>j<sup>​​​​​​</sup></code> 项任务 <strong>所需要的时间</strong>（单位：秒）。</p>\n",
    "\n",
    "<p>你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 <code>0</code> 项任务在第 <code>0</code> 秒可以开始处理，相应地，第 <code>j</code> 项任务在第 <code>j</code> 秒可以开始处理。处理第 <code>j</code> 项任务时，你需要为它分配一台 <strong>权重最小</strong> 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 <strong>下标最小</strong> 的服务器。如果一台空闲服务器在第 <code>t</code> 秒分配到第 <code>j</code> 项任务，那么在 <code>t + tasks[j]</code> 时它将恢复空闲状态。</p>\n",
    "\n",
    "<p>如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 <strong>尽可能早</strong> 地处理剩余任务。 如果有多项任务等待分配，则按照 <strong>下标递增</strong> 的顺序完成分配。</p>\n",
    "\n",
    "<p>如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。</p>\n",
    "\n",
    "<p>构建长度为 <code>m</code> 的答案数组 <code>ans</code> ，其中 <code>ans[j]</code> 是第 <code>j</code> 项任务分配的服务器的下标。</p>\n",
    "\n",
    "<p>返回答案数组<em> </em><code>ans</code>​​​​ 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>servers = [3,3,2], tasks = [1,2,3,2,1,2]\n",
    "<strong>输出：</strong>[2,2,0,2,1,2]\n",
    "<strong>解释：</strong>事件按时间顺序如下：\n",
    "- 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。\n",
    "- 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。\n",
    "- 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。\n",
    "- 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。\n",
    "- 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。\n",
    "- 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]\n",
    "<strong>输出：</strong>[1,4,1,4,1,3,2]\n",
    "<strong>解释：</strong>事件按时间顺序如下：\n",
    "- 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。\n",
    "- 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。\n",
    "- 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。\n",
    "- 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。\n",
    "- 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。\n",
    "- 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。\n",
    "- 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>servers.length == n</code></li>\n",
    "\t<li><code>tasks.length == m</code></li>\n",
    "\t<li><code>1 <= n, m <= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= servers[i], tasks[j] <= 2 * 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [process-tasks-using-servers](https://leetcode.cn/problems/process-tasks-using-servers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [process-tasks-using-servers](https://leetcode.cn/problems/process-tasks-using-servers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,3,2]\\n[1,2,3,2,1,2]', '[5,1,4,3,2]\\n[2,1,2,4,5,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        heap = []\n",
    "        for i in range(len(servers)):\n",
    "            heapq.heappush(heap, (servers[i], i))\n",
    "        ans = [0]*len(tasks)\n",
    "        heap2 = []\n",
    "        cur = 0\n",
    "        for j in range(len(tasks)):\n",
    "            cur = max(cur, j)\n",
    "            while heap2:\n",
    "                t, q, i = heapq.heappop(heap2)\n",
    "                if t <= cur:\n",
    "                    heapq.heappush(heap, (servers[i], i))\n",
    "                else:\n",
    "                    heapq.heappush(heap2, (t,q,i))\n",
    "                    break\n",
    "            if heap:\n",
    "                q, i = heapq.heappop(heap)\n",
    "                ans[j] = i\n",
    "                heapq.heappush(heap2, (cur+tasks[j], q, i))\n",
    "            else:\n",
    "                t, q, i = heapq.heappop(heap2)\n",
    "                cur = t\n",
    "                ans[j] = i\n",
    "                heapq.heappush(heap2, (t+tasks[j], q, i))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        waiting = []\n",
    "        work = []\n",
    "        for i, s in enumerate(servers):\n",
    "            heappush(waiting, (s, i))\n",
    "        \n",
    "        m = len(tasks)\n",
    "        ans = [0] * m\n",
    "        i = 0\n",
    "        for time in range(m):\n",
    "            while work and work[0][0] == time:\n",
    "                _, s, x = heappop(work)\n",
    "                heappush(waiting, (s, x))\n",
    "            while waiting and i <= time:\n",
    "                ans[i] = waiting[0][1]\n",
    "                s, x = heappop(waiting)\n",
    "                heappush(work, (time + tasks[i], s, x))\n",
    "                i += 1\n",
    "        \n",
    "        while i < m:\n",
    "            time = work[0][0]\n",
    "            while work and work[0][0] == time:\n",
    "                _, s, x = heappop(work)\n",
    "                heappush(waiting, (s, x))\n",
    "            while waiting and i < m:\n",
    "                ans[i] = waiting[0][1]\n",
    "                s, x = heappop(waiting)\n",
    "                heappush(work, (time + tasks[i], s, x))\n",
    "                i += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        busy = []\n",
    "        idle = []\n",
    "        for i, w in enumerate(servers):\n",
    "            heappush(idle, (w, i))\n",
    "        \n",
    "        ans = [0] * len(tasks)\n",
    "        timecurrent = 0\n",
    "        for i, dur in enumerate(tasks):\n",
    "            timecurrent = max(timecurrent, i)\n",
    "            #@print(timecurrent, idle, busy)\n",
    "            while busy and busy[0][0] <= timecurrent:\n",
    "                time, idx = heappop(busy)\n",
    "                heappush(idle, (servers[idx], idx))\n",
    "            if not idle:\n",
    "                timecurrent = busy[0][0]\n",
    "                while busy and busy[0][0] <= timecurrent:\n",
    "                    time, idx = heappop(busy)\n",
    "                    heappush(idle, (servers[idx], idx))\n",
    "                    #print(i, idx, servers[idx])\n",
    "            \n",
    "            t = heappop(idle)\n",
    "            ans[i] = t[1]\n",
    "            heappush(busy, (timecurrent + dur, t[1]))\n",
    "            #print(timecurrent, idle, busy)\n",
    "        return ans\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        serversAmount = len(servers)\n",
    "        tasksAmount = len(tasks)\n",
    "        idle = [(servers[i], i) for i in range(serversAmount)]\n",
    "        heapify(idle)\n",
    "        using = [] # (endTime, serverId)\n",
    "        res = []\n",
    "        latestTime = 0\n",
    "\n",
    "        def release():\n",
    "            while using and using[0][0] <= latestTime:\n",
    "                _, serverId = heappop(using)\n",
    "                heappush(idle, (servers[serverId], serverId))\n",
    "\n",
    "        for i in range(tasksAmount):\n",
    "            latestTime = max(latestTime, i)\n",
    "            release()\n",
    "            \n",
    "            if len(idle) == 0:\n",
    "                latestTime = using[0][0]\n",
    "                release()\n",
    "\n",
    "            _, serverId = heappop(idle) \n",
    "            heappush(using, (latestTime+tasks[i], serverId))\n",
    "            res.append(serverId)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        waiting = [(s, i) for i, s in enumerate(servers)]\n",
    "        heapify(waiting)\n",
    "\n",
    "        work = []\n",
    "        \n",
    "        m = len(tasks)\n",
    "        ans = [0] * m\n",
    "        time = 0\n",
    "        for i, task in enumerate(tasks):\n",
    "            time = max(time, i)\n",
    "            while work and work[0][0] == time:\n",
    "                _, s, x = heappop(work)\n",
    "                heappush(waiting, (s, x))\n",
    "            if not waiting:\n",
    "                time = work[0][0]\n",
    "                while work and work[0][0] == time:\n",
    "                    _, s, x = heappop(work)\n",
    "                    heappush(waiting, (s, x))\n",
    "            \n",
    "            s, x = heappop(waiting)\n",
    "            ans[i] = x\n",
    "            heappush(work, (task + time, s, x))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \n",
    "        from heapq import heapify,heappush,heappop\n",
    "\n",
    "        m,n=len(tasks),len(servers)\n",
    "        \n",
    "        ans=[]\n",
    "\n",
    "        q=collections.deque()\n",
    "        \n",
    "        av,re=[],[]\n",
    "        heapify(av)\n",
    "        heapify(re)\n",
    "\n",
    "        for si,sw in enumerate(servers):\n",
    "            heappush(av,(sw,si))\n",
    "        \n",
    "        for t in range(m):\n",
    "            q.append((tasks[t],t))\n",
    "            while re and re[0][0]<=t:\n",
    "                _,sw,si=heappop(re)\n",
    "                heappush(av,(sw,si))\n",
    "            while av and q:\n",
    "                nt,t_nu=q.popleft()\n",
    "                sw,si=heappop(av)\n",
    "                ans.append(si)\n",
    "                heappush(re,(nt+t,sw,si))\n",
    "        \n",
    "        while q:\n",
    "            nt,_=q.popleft()\n",
    "            t,sw,si=heappop(re)\n",
    "            ans.append(si)\n",
    "            t+=nt\n",
    "            heappush(re,(t,sw,si))\n",
    "            \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        n, m = len(servers), len(tasks)\n",
    "        idle = [(servers[i], i) for i in range(n)]\n",
    "        heapify(idle)\n",
    "        using = [] # (endTime, weight, serverId)\n",
    "        ans = [0] * m\n",
    "\n",
    "        for i, during in enumerate(tasks):\n",
    "            while using and using[0][0] <= i:\n",
    "                _, weight, serverId = heappop(using)\n",
    "                heappush(idle, (weight, serverId))\n",
    "            latency = 0\n",
    "            if not idle:\n",
    "                recentEndTime, weight, serverId = heappop(using)\n",
    "                latency = recentEndTime - i \n",
    "            else:\n",
    "                weight, serverId = heappop(idle)\n",
    "            heappush(using, (i+tasks[i]+latency, weight, serverId))\n",
    "            ans[i] = serverId\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(tasks)\n",
    "        ret = [0] * n\n",
    "        m = len(servers)\n",
    "        due = [(0, servers[i], i) for i in range(m)]\n",
    "        heapify(due)\n",
    "        # ret[tasks[0]] = 0\n",
    "        q = []\n",
    "        now = 0\n",
    "        for i in range(n):\n",
    "            # now += 1\n",
    "            now = max(now, i)\n",
    "            while due and due[0][0] <= now:\n",
    "                d, w, idx = heappop(due)\n",
    "                heappush(q, (w, idx, d)) \n",
    "            if not q:\n",
    "                d, w, idx = heappop(due)\n",
    "                now = d\n",
    "                heappush(q, (w, idx, d))\n",
    "            # print(i, tasks[i], q, due, now, end='====')    \n",
    "            w, idx, d = heappop(q)\n",
    "            ret[i] = idx\n",
    "            heappush(due, (now + tasks[i], w, idx))\n",
    "            # print(now, q, due, due and due[0][0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(tasks)\n",
    "        ret = [0] * n\n",
    "        m = len(servers)\n",
    "        due = [(0, servers[i], i) for i in range(m)]\n",
    "        heapify(due)\n",
    "        # ret[tasks[0]] = 0\n",
    "        q = []\n",
    "        now = 0\n",
    "        for i in range(n):\n",
    "            # now += 1\n",
    "            now = max(now, i)\n",
    "            while due and due[0][0] <= now:\n",
    "                d, w, idx = heappop(due)\n",
    "                heappush(q, (w, idx, d)) \n",
    "            if not q:\n",
    "                d, w, idx = heappop(due)\n",
    "                heappush(q, (w, idx, d))\n",
    "            # print(i, tasks[i], q, due, now, end='====')    \n",
    "            w, idx, d = heappop(q)\n",
    "            now = max(now, d)\n",
    "            ret[i] = idx\n",
    "            heappush(due, (now + tasks[i], w, idx))\n",
    "            # print(now, q, due, due and due[0][0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        busy = []\n",
    "        idle = [(servers[i], i) for i in range(len(servers))]\n",
    "        heapq.heapify(idle)\n",
    "\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "\n",
    "\n",
    "        ts = 0\n",
    "        res = []\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            res.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        h = []\n",
    "        h_cost = []\n",
    "        ans = []\n",
    "        for i, v in enumerate(servers) :\n",
    "            heappush(h_cost, (v, i))\n",
    "        pre = 0\n",
    "        for i, v in enumerate(tasks) :\n",
    "            pre = max(pre, i)\n",
    "            while h and h[0][0] <= pre :\n",
    "                top, ind = heappop(h)\n",
    "                heappush(h_cost, (servers[ind], ind))\n",
    "\n",
    "            if not h_cost :\n",
    "                pre = h[0][0]\n",
    "                while h and h[0][0] <= pre :\n",
    "                    top, ind = heappop(h)\n",
    "                    heappush(h_cost, (servers[ind], ind))\n",
    "\n",
    "            cost, ind = heappop(h_cost)\n",
    "            heappush(h, (pre+v, ind))\n",
    "\n",
    "            ans.append(ind)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        busy = list()\n",
    "\n",
    "        idle = [(w,i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "\n",
    "        ts = 0\n",
    "\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        res = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            res.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        busy, idle, cur, result = [], [(server, i) for i, server in enumerate(servers)], 0, []\n",
    "        heapify(idle)\n",
    "        for i, task in enumerate(tasks):\n",
    "            cur = max(cur, i)\n",
    "            while (busy and busy[0][0] <= cur) or not idle:\n",
    "                cur, idx = heappop(busy)\n",
    "                heappush(idle, (servers[idx], idx))\n",
    "            _, idx = heappop(idle)\n",
    "            result.append(idx)\n",
    "            heappush(busy, (cur + task, idx))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 空闲服务器，存储(w, i)，w越小优先级越高，再按照i排列\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        busy = []  # 繁忙服务器, 存储(t, i)，t越小优先级越高，再按照i排列\n",
    "\n",
    "        res = []\n",
    "        t = 0\n",
    "\n",
    "        # 根据时间，更新空闲服务器\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= t:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "\n",
    "        for i, task_t in enumerate(tasks):\n",
    "            # 直接找到最大的可行时间\n",
    "            t = max(t, i)\n",
    "            # 每次更新时间，都要更新两个服务器\n",
    "            release()\n",
    "            # 无空闲服务器，找到最开始有空闲服务器的时刻\n",
    "            if not idle:\n",
    "                t = busy[0][0]\n",
    "                # 可能同时前n个服务器都是一个时间空闲，因此要及时更新服务器\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            res.append(idx)\n",
    "            heapq.heappush(busy, (t+task_t, idx))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 工作中的服务器，存储二元组 (t, idx)\n",
    "        busy = list()\n",
    "        \n",
    "        # 空闲的服务器，存储二元组 (w, idx)\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        \n",
    "        ts = 0\n",
    "        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        ans = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 优先队列\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 工作中的服务器，存储二元组 (t, idx)\n",
    "        busy = []\n",
    "        \n",
    "        # 空闲的服务器，存储二元组 (w, idx)\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        \n",
    "        ts = 0\n",
    "        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        ans = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\r\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\r\n",
    "        heapify(idle)\r\n",
    "        ts = 0\r\n",
    "        busy = []\r\n",
    "        res = []\r\n",
    "\r\n",
    "        for i, t in enumerate(tasks):\r\n",
    "            ts = max(ts, i)\r\n",
    "            if not idle:\r\n",
    "                ts = busy[0][0]\r\n",
    "            while busy and busy[0][0] <= ts:\r\n",
    "                _, idx = heappop(busy)\r\n",
    "                heappush(idle, (servers[idx], idx))\r\n",
    "            _, idx = heappop(idle)\r\n",
    "            res.append(idx)\r\n",
    "            heappush(busy, (ts + t, idx))\r\n",
    "        return res \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        def release():\n",
    "            # 将时间小于时间戳的任务全部释放\n",
    "            while busy and busy[0][0] <= timestamp:\n",
    "                _,idx = heapq.heappop(busy)\n",
    "                heapq.heappush(relax,(servers[idx],idx))\n",
    "\n",
    "        # 工作服务器\n",
    "        busy = []\n",
    "        # 空闲服务器\n",
    "        ans = []\n",
    "        relax =  [(w,i) for i,w in enumerate(servers)]\n",
    "        heapq.heapify(relax)\n",
    "        # 处理任务\n",
    "        timestamp = 0 # 时间戳\n",
    "        for i,v in enumerate(tasks):\n",
    "            # 释放工作服务器中已经完成任务的服务器\n",
    "            timestamp = max(timestamp,i)\n",
    "            release()\n",
    "            if not relax:\n",
    "                timestamp = busy[0][0]\n",
    "                release()\n",
    "            # 从空闲服务器中弹出\n",
    "            _,idx = heapq.heappop(relax)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy,(timestamp+v,idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 工作中的服务器，存储二元组 (t, idx)\n",
    "        busy = list()\n",
    "        \n",
    "        # 空闲的服务器，存储二元组 (w, idx)\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        \n",
    "        ts = 0\n",
    "        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        ans = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Heap. Time O((m+n)logm) (mlogm for init idle, nlogm for move n tasks) Space O(m)\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # busy: [(available time, serverIdx)]; idle: [(weight, i)]\n",
    "        busy, idle = [], []\n",
    "        for serverIdx, weight in enumerate(servers):\n",
    "            heappush(idle, (weight, serverIdx))\n",
    "        # move servers who completed tasks from busy to idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, serverIdx = heappop(busy)\n",
    "                heappush(idle, (servers[serverIdx], serverIdx))\n",
    "        ts = 0\n",
    "        res = []\n",
    "        for i, task in enumerate(tasks):\n",
    "            # jump to task start time if needed\n",
    "            ts = max(ts, i)\n",
    "            # release servers first\n",
    "            release()\n",
    "            # if still no idle server, jump to first release time\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            # assign task to the first idle server, record, move it to busy\n",
    "            _, serverIdx = heappop(idle)\n",
    "            res.append(serverIdx)\n",
    "            heappush(busy, (ts + task, serverIdx))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        busy = PriorityQueue()\n",
    "        idle = PriorityQueue()\n",
    "        for i, weight in enumerate(servers):\n",
    "            idle.put((weight, i))\n",
    "        ans = []\n",
    "        time = 0\n",
    "        for i, task in enumerate(tasks):\n",
    "            time = max(time, i)\n",
    "            while busy.queue and busy.queue[0][0] <= time:\n",
    "                _, index = busy.get()\n",
    "                idle.put((servers[index], index))\n",
    "            if not idle.queue:\n",
    "                time = busy.queue[0][0]\n",
    "                while busy.queue and busy.queue[0][0] <= time:\n",
    "                    _, index = busy.get()\n",
    "                    idle.put((servers[index], index))\n",
    "            _, index = idle.get()\n",
    "            ans.append(index)\n",
    "            busy.put((time+task, index))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        n = len(servers)\n",
    "        m = len(tasks)\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        time = 0\n",
    "        busy = list()\n",
    "        avi = list()\n",
    "        for i in range(n):\n",
    "            avi.append((servers[i],i))\n",
    "        heapq.heapify(avi)\n",
    "        wait = []\n",
    "        while cur < m:\n",
    "            time = max(time,cur)\n",
    "            while 1:\n",
    "                if len(busy) > 0:\n",
    "                    top = heapq.heappop(busy)\n",
    "                else:\n",
    "                    break\n",
    "                if top[0] > time:\n",
    "                    heapq.heappush(busy,top)\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappush(avi,(servers[top[1]],top[1]))\n",
    "            if not avi:\n",
    "                time = busy[0][0]\n",
    "                while 1:\n",
    "                    if len(busy) > 0:\n",
    "                        top = heapq.heappop(busy)\n",
    "                    else:\n",
    "                        break\n",
    "                    if top[0] > time:\n",
    "                        heapq.heappush(busy,top)\n",
    "                        break\n",
    "                    else:\n",
    "                        heapq.heappush(avi,(servers[top[1]],top[1]))\n",
    "            \n",
    "            ma = heapq.heappop(avi)[1]\n",
    "            ans.append(ma)\n",
    "            heapq.heappush(busy,(time+tasks[cur],ma))\n",
    "            cur = cur + 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # busy: [(available time, serverIdx)]; idle: [(weight, i)]\n",
    "        busy, idle = [], []\n",
    "        for serverIdx, weight in enumerate(servers):\n",
    "            heappush(idle, (weight, serverIdx))\n",
    "        # move servers who completed tasks from busy to idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, serverIdx = heappop(busy)\n",
    "                heappush(idle, (servers[serverIdx], serverIdx))\n",
    "        ts = 0\n",
    "        res = []\n",
    "        for i, task in enumerate(tasks):\n",
    "            # jump to task start time if needed\n",
    "            ts = max(ts, i)\n",
    "            # release servers first\n",
    "            release()\n",
    "            # if still no idle server, jump to first release time\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            # assign task to the first idle server, record, move it to busy\n",
    "            _, serverIdx = heappop(idle)\n",
    "            res.append(serverIdx)\n",
    "            heappush(busy, (ts + task, serverIdx))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 工作中的服务器，存储二元组 (t, idx)\n",
    "        busy = list()\n",
    "        \n",
    "        # 空闲的服务器，存储二元组 (w, idx)\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        \n",
    "        ts = 0\n",
    "        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        ans = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 工作中的服务器，存储二元组 (t, idx)\n",
    "        busy = list()\n",
    "        \n",
    "        # 空闲的服务器，存储二元组 (w, idx)\n",
    "        idle = [(w, i) for i, w in enumerate(servers)]\n",
    "        heapq.heapify(idle)\n",
    "        \n",
    "        ts = 0\n",
    "        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "        def release():\n",
    "            while busy and busy[0][0] <= ts:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "        ans = list()\n",
    "        for i, task in enumerate(tasks):\n",
    "            ts = max(ts, i)\n",
    "            release()\n",
    "            if not idle:\n",
    "                ts = busy[0][0]\n",
    "                release()\n",
    "            \n",
    "            _, idx = heapq.heappop(idle)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        # 创建一个元组的列表，其中元组的第一个元素是服务器的权重，第二个元素是服务器的索引\n",
    "        available_servers = [(weight, i) for i, weight in enumerate(servers)]\n",
    "        # 将其转换为优先队列\n",
    "        heapq.heapify(available_servers)\n",
    "        \n",
    "        # 用于存储何时服务器将成为空闲的优先队列\n",
    "        busy_servers = []\n",
    "        \n",
    "        # 用于存储结果的列表\n",
    "        res = []\n",
    "        \n",
    "        for t, task_time in enumerate(tasks):\n",
    "            # 如果有服务器在此时变为可用，则将其添加回available_servers队列\n",
    "            while busy_servers and busy_servers[0][0] <= t:\n",
    "                time, weight, i = heapq.heappop(busy_servers)\n",
    "                heapq.heappush(available_servers, (weight, i))\n",
    "            \n",
    "            # 如果没有可用的服务器，我们必须等待下一个服务器\n",
    "            if not available_servers:\n",
    "                time, weight, i = heapq.heappop(busy_servers)\n",
    "                heapq.heappush(available_servers, (weight, i))\n",
    "                t = time # 跳转到下一个可用的服务器时间\n",
    "                \n",
    "            # 从available_servers取出一个服务器并添加到结果中\n",
    "            weight, i = heapq.heappop(available_servers)\n",
    "            res.append(i)\n",
    "            \n",
    "            # 将服务器添加到busy_servers，记录它将何时再次可用\n",
    "            heapq.heappush(busy_servers, (t + task_time, weight, i))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        q = []\n",
    "        for i, s in enumerate(servers):\n",
    "            heapq.heappush(q, (s, i))\n",
    "        used = []\n",
    "        ans = []\n",
    "        time = 0\n",
    "        for i, t in enumerate(tasks):\n",
    "            time = max(time, i)\n",
    "            while used and used[0][0] <= time:\n",
    "                _, idx = heapq.heappop(used)\n",
    "                heapq.heappush(q, (servers[idx], idx))\n",
    "            if not q:\n",
    "                time = used[0][0]\n",
    "                while used and used[0][0] <= time:\n",
    "                    _, idx = heapq.heappop(used)\n",
    "                    heapq.heappush(q, (servers[idx], idx))\n",
    "            _, idx = heapq.heappop(q)\n",
    "            ans.append(idx)\n",
    "            heapq.heappush(used, (time + t, idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        q = []\n",
    "        for i, s in enumerate(servers):\n",
    "            heapq.heappush(q, (s, i))\n",
    "        used = []\n",
    "        ans = []\n",
    "        time = 0\n",
    "        for i, t in enumerate(tasks):\n",
    "            while used and used[0][0] <= i:\n",
    "                _, _, idx = heapq.heappop(used)\n",
    "                heapq.heappush(q, (servers[idx], idx))\n",
    "            if q:\n",
    "                _, idx = heapq.heappop(q)\n",
    "                ans.append(idx)\n",
    "                heapq.heappush(used, (i + t, servers[idx], idx))\n",
    "            else:\n",
    "                nt, _, idx = heapq.heappop(used)\n",
    "                ans.append(idx)\n",
    "                heapq.heappush(used, (nt + t, servers[idx], idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        q = []\n",
    "        for i, s in enumerate(servers):\n",
    "            heapq.heappush(q, (s, i))\n",
    "        used = []\n",
    "        ans = []\n",
    "        time = 0\n",
    "        for i, t in enumerate(tasks):\n",
    "            while used and used[0][0] <= i:\n",
    "                _, _, idx = heapq.heappop(used)\n",
    "                heapq.heappush(q, (servers[idx], idx))\n",
    "            if q:\n",
    "                _, idx = heapq.heappop(q)\n",
    "                ans.append(idx)\n",
    "                heapq.heappush(used, (i + t, servers[idx], idx))\n",
    "            else:\n",
    "                nt, _, idx = heapq.heappop(used)\n",
    "                ans.append(idx)\n",
    "                heapq.heappush(used, (nt + t, servers[idx], idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        busy, idle, cur, result = [], [(server, i) for i, server in enumerate(servers)], 0, []\n",
    "        heapify(idle)\n",
    "        for i, task in enumerate(tasks):\n",
    "            cur = max(cur, i)\n",
    "            while busy and busy[0][0] <= cur:\n",
    "                _, idx = heapq.heappop(busy)\n",
    "                heappush(idle, (servers[idx], idx))\n",
    "            if not idle:\n",
    "                cur = busy[0][0]\n",
    "                while busy and busy[0][0] <= cur:\n",
    "                    _, idx = heapq.heappop(busy)\n",
    "                    heappush(idle, (servers[idx], idx))\n",
    "            _, idx = heappop(idle)\n",
    "            result.append(idx)\n",
    "            heappush(busy, (cur + task, idx))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        pq = []\n",
    "        for i,s in enumerate(servers):\n",
    "            heapq.heappush(pq, (s, i))\n",
    "        use = []\n",
    "        for base, task in enumerate(tasks):\n",
    "            while use and use[0][0] <= base:\n",
    "                _,s,i = heapq.heappop(use)\n",
    "                heapq.heappush(pq, (s, i))\n",
    "            if pq:\n",
    "                s,i = heapq.heappop(pq)\n",
    "                ans.append(i)\n",
    "                heapq.heappush(use, (base+task, s, i))\n",
    "            else:\n",
    "                t, s, i = heapq.heappop(use)\n",
    "                ans.append(i)\n",
    "                heapq.heappush(use, (t + task, s, i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 如果多个using中的endTime是一样的，但是释放顺序是根据endTime和Id来的，没有考虑到权重的影响\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        serversAmount = len(servers)\n",
    "        tasksAmount = len(tasks)\n",
    "        idle = [(servers[i], i) for i in range(serversAmount)]\n",
    "        heapify(idle)\n",
    "        using = [] # (endTime, serverId)\n",
    "        res = []\n",
    "\n",
    "        for i in range(tasksAmount):\n",
    "            while using and using[0][0] <= i:\n",
    "                _, weight, serverId = heappop(using)\n",
    "                heappush(idle, (servers[serverId], serverId))\n",
    "            latency = 0\n",
    "            if len(idle) == 0:\n",
    "                endTime, weight, serverId = heappop(using)\n",
    "                latency = endTime - i \n",
    "            else:\n",
    "                _, serverId = heappop(idle)\n",
    "\n",
    "            heappush(using, (i+tasks[i]+latency, servers[serverId], serverId))\n",
    "            res.append(serverId)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \"\"\" Heap queue \"\"\"\n",
    "        # store the info to the server into a heap \n",
    "        deque_idle = []  # idle \n",
    "        deque_use = []  # in use \n",
    "        for i, j in enumerate(servers):\n",
    "            deque_idle.append((j, i))\n",
    "\n",
    "        heapq.heapify(deque_idle)\n",
    "        heapq.heapify(deque_use)\n",
    "\n",
    "        ans = []\n",
    "        for basetime, task in enumerate(tasks):\n",
    "            # pop all the finished servers from deque use to deque idle \n",
    "            while deque_use and deque_use[0][0] <= basetime:\n",
    "                (curr_time, curr_w, curr_i) = heapq.heappop(deque_use)\n",
    "                heapq.heappush(deque_idle, (curr_w, curr_i))\n",
    "\n",
    "            # if we have idle server heap \n",
    "            if deque_idle:\n",
    "                curr_w, curr_i = heapq.heappop(deque_idle)\n",
    "                ans.append(curr_i)\n",
    "                # move this server to use deque \n",
    "                heapq.heappush(deque_use, (basetime+task, curr_w, curr_i))\n",
    "            # no single server is idle\n",
    "            else:\n",
    "                (curr_time, curr_w, curr_i) = heapq.heappop(deque_use)\n",
    "                ans.append(curr_i)\n",
    "                heapq.heappush(deque_use, (curr_time+task, curr_w, curr_i))\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "    \n",
    "    from heapq import heapify,heappush,heappop\n",
    "\n",
    "    m,n=len(tasks),len(servers)\n",
    "    \n",
    "    ans=[]\n",
    "\n",
    "    q=collections.deque()\n",
    "    \n",
    "    av,re=[(sw,si) for si,sw in enumerate(servers)],[]\n",
    "    heapify(av)\n",
    "    heapify(re)\n",
    "\n",
    "    t_n=0\n",
    "    def rel():\n",
    "      while re and re[0][0]<=t_n:\n",
    "        _,sw,si=heappop(re)\n",
    "        heappush(av,(sw,si))\n",
    "\n",
    "    for t in range(m):\n",
    "      t_n=max(t,t_n)\n",
    "      q.append(tasks[t])\n",
    "      rel()\n",
    "      if not av:\n",
    "        t_n=re[0][0]\n",
    "        rel()\n",
    "      while av and q:\n",
    "        sw,si=heappop(av)\n",
    "        ans.append(si)\n",
    "        needt=q.popleft()\n",
    "        heappush(re,(needt+t_n,sw,si))\n",
    "\n",
    "    return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        # servers = [[s, i] for i, s in enumerate(servers)]\n",
    "        # heapq.heapify(servers)\n",
    "\n",
    "        # working = []\n",
    "        # pending = Deque()\n",
    "\n",
    "        # ret = [0] * len(tasks) \n",
    "\n",
    "        # i = 0\n",
    "        # while i < len(tasks) or pending:\n",
    "\n",
    "        #     if i < len(tasks):\n",
    "        #         pending.append((i, tasks[i]))\n",
    "\n",
    "        #     while working and working[0][0] == i:\n",
    "        #         heapq.heappush(servers, heapq.heappop(working)[1:])\n",
    "\n",
    "        #     while servers and pending:\n",
    "        #         task, time = pending.popleft()\n",
    "        #         s, idx = heapq.heappop(servers)\n",
    "                \n",
    "        #         ret[task] = idx\n",
    "        #         heapq.heappush(working, [i + time, s, idx])\n",
    "\n",
    "        #     if i < len(tasks):\n",
    "        #         i += 1\n",
    "        #     else:\n",
    "        #         i = working[0][0]\n",
    "        \n",
    "        # return ret\n",
    "\n",
    "        # use dict to record working, 2000ms\n",
    "        # use heap to record working, 1100ms\n",
    "\n",
    "        # from answer 832 ms\n",
    "\n",
    "# class Solution:\n",
    "#     def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "#         # 工作中的服务器，存储二元组 (t, idx)\n",
    "#         busy = list()\n",
    "        \n",
    "#         # 空闲的服务器，存储二元组 (w, idx)\n",
    "#         idle = [(w, i) for i, w in enumerate(servers)]\n",
    "#         heapq.heapify(idle)\n",
    "        \n",
    "#         ts = 0\n",
    "#         # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle\n",
    "#         def release():\n",
    "#             while busy and busy[0][0] <= ts:\n",
    "#                 _, idx = heapq.heappop(busy)\n",
    "#                 heapq.heappush(idle, (servers[idx], idx))\n",
    "        \n",
    "#         ans = list()\n",
    "#         for i, task in enumerate(tasks):\n",
    "#             ts = max(ts, i)\n",
    "#             release()\n",
    "#             if not idle:\n",
    "#                 ts = busy[0][0]\n",
    "#                 release()\n",
    "            \n",
    "#             _, idx = heapq.heappop(idle)\n",
    "#             ans.append(idx)\n",
    "#             heapq.heappush(busy, (ts + task, idx))\n",
    "        \n",
    "#         return ans\n",
    "\n",
    "# from another answer\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        pq = []\n",
    "        for i,s in enumerate(servers):\n",
    "            heapq.heappush(pq, (s, i))\n",
    "        use = []\n",
    "        for base, task in enumerate(tasks):\n",
    "            while use and use[0][0] <= base:\n",
    "                _,s,i = heapq.heappop(use)\n",
    "                heapq.heappush(pq, (s, i))\n",
    "            if pq:\n",
    "                s,i = heapq.heappop(pq)\n",
    "                ans.append(i)\n",
    "                heapq.heappush(use, (base+task, s, i))\n",
    "            else:\n",
    "                t, s, i = heapq.heappop(use)\n",
    "                ans.append(i)\n",
    "                heapq.heappush(use, (t + task, s, i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        null = [[servers[i], i] for i in range(len(servers))]\n",
    "        heapq.heapify(null)\n",
    "        n = len(tasks)\n",
    "        ans = [-1]*n\n",
    "        busy = []\n",
    "        cur = 0\n",
    "        for j in range(n):\n",
    "            if cur < j:\n",
    "                cur = j\n",
    "            while busy and busy[0][0] <= cur:\n",
    "                _, i = heapq.heappop(busy)\n",
    "                heapq.heappush(null, [servers[i], i])\n",
    "            if not null:\n",
    "                tm = busy[0][0]\n",
    "                cur = tm\n",
    "                while busy and busy[0][0] == tm:\n",
    "                    t, i = heapq.heappop(busy)\n",
    "                    heapq.heappush(null, [servers[i], i])\n",
    "\n",
    "            _, i = heapq.heappop(null)\n",
    "            ans[j] = i\n",
    "            heapq.heappush(busy, [cur+tasks[j], i])\n",
    " \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        s = [] # [weight, idx]\n",
    "        for i in range(len(servers)): heappush(s, [servers[i], i])\n",
    "        q = [] # [free_time, idx]\n",
    "\n",
    "        ans = []\n",
    "        cur = 0\n",
    "\n",
    "        def release():\n",
    "            while q and q[0][0] <= cur:\n",
    "                i = heappop(q)[1]\n",
    "                heappush(s, [servers[i], i])\n",
    "\n",
    "        for j in range(len(tasks)):\n",
    "            cur = max(cur, j)\n",
    "            release()\n",
    "            if not s:\n",
    "                cur = q[0][0]\n",
    "                release()\n",
    "\n",
    "            i = heappop(s)[1]\n",
    "            ans.append(i)\n",
    "            heappush(q, [cur + tasks[j], i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \"\"\" n = len(servers)\n",
    "        m = len(tasks)\n",
    "        stack = [[0,servers[i],i] for i in range(n)]\n",
    "        heapq.heapify(stack)\n",
    "        time = 0\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while len(ans) < m:\n",
    "            if time < stack[0][0]:\n",
    "                time = stack[0][0]\n",
    "            while stack[0][0] < time:\n",
    "                tm,a,b = heapq.heappop(stack)\n",
    "                heapq.heappush(stack,[time,a,b])\n",
    "            while i <= time and i < m and stack[0][0] == time:\n",
    "                tm,a,b = heapq.heappop(stack)\n",
    "                ans.append(b)\n",
    "                heapq.heappush(stack, [time+tasks[i],a,b])\n",
    "                i += 1\n",
    "            time += 1\n",
    "        return ans \"\"\"\n",
    "\n",
    "        n = len(servers)\n",
    "        m = len(tasks)\n",
    "        stack1 = [[servers[i],i] for i in range(n)]  #idle\n",
    "        stack2 = []                                  #occupied\n",
    "        heapq.heapify(stack1)\n",
    "        time = 0\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while len(ans) < m:\n",
    "            if not stack1:\n",
    "                time = stack2[0][0]\n",
    "            while stack2 and stack2[0][0] <= time:\n",
    "                _, a = heapq.heappop(stack2)\n",
    "                heapq,heappush(stack1, [servers[a],a])\n",
    "            while i <= time and i < m and stack1:\n",
    "                a,b = heapq.heappop(stack1)\n",
    "                ans.append(b)\n",
    "                heapq.heappush(stack2, [time+tasks[i],b])\n",
    "                i += 1\n",
    "            time += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \"\"\" n = len(servers)\n",
    "        m = len(tasks)\n",
    "        stack = [[0,servers[i],i] for i in range(n)]\n",
    "        heapq.heapify(stack)\n",
    "        time = 0\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while len(ans) < m:\n",
    "            if time < stack[0][0]:\n",
    "                time = stack[0][0]\n",
    "            while stack[0][0] < time:\n",
    "                tm,a,b = heapq.heappop(stack)\n",
    "                heapq.heappush(stack,[time,a,b])\n",
    "            while i <= time and i < m and stack[0][0] == time:\n",
    "                tm,a,b = heapq.heappop(stack)\n",
    "                ans.append(b)\n",
    "                heapq.heappush(stack, [time+tasks[i],a,b])\n",
    "                i += 1\n",
    "            time += 1\n",
    "        return ans \"\"\"\n",
    "\n",
    "        n = len(servers)\n",
    "        m = len(tasks)\n",
    "        stack1 = [[servers[i],i] for i in range(n)]  #idle\n",
    "        stack2 = []                                  #occupied\n",
    "        heapq.heapify(stack1)\n",
    "        time = 0\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while len(ans) < m:\n",
    "            if not stack1:\n",
    "                time = stack2[0][0]\n",
    "            while stack2 and stack2[0][0] == time:\n",
    "                _, a = heapq.heappop(stack2)\n",
    "                heapq,heappush(stack1, [servers[a],a])\n",
    "            while i <= time and i < m and stack1:\n",
    "                a,b = heapq.heappop(stack1)\n",
    "                ans.append(b)\n",
    "                heapq.heappush(stack2, [time+tasks[i],b])\n",
    "                i += 1\n",
    "            time += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        q0 = queue.PriorityQueue()\n",
    "        for i in range(len(servers)):\n",
    "            q0.put([servers[i],i])\n",
    "        q1 = queue.PriorityQueue()\n",
    "        ans = []\n",
    "        for i in range(len(tasks)):\n",
    "            while not q1.empty():\n",
    "                front = q1.queue[0]\n",
    "                if front[0] <= i:\n",
    "                    tmp = q1.get()\n",
    "                    q0.put([tmp[1],tmp[2]])\n",
    "                else:\n",
    "                    break\n",
    "            if not q0.empty():\n",
    "                sv = q0.get()\n",
    "                ans.append(sv[1])\n",
    "                q1.put([i+tasks[i],sv[0],sv[1]])\n",
    "            else:\n",
    "                sv = q1.get()\n",
    "                ans.append(sv[2])\n",
    "                q1.put([sv[0]+tasks[i],sv[1],sv[2]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        heap, work = [[j,i] for i,j in enumerate(servers)], []\n",
    "        heapify(heap)\n",
    "        res = []\n",
    "        for i,v in enumerate(tasks):\n",
    "            while work and work[0][0] <= i:\n",
    "                a, b, c = heapq.heappop(work)\n",
    "                heapq.heappush(heap, [b,c])\n",
    "            if heap:\n",
    "                b, c = heapq.heappop(heap)\n",
    "                a = i            \n",
    "            else:\n",
    "                a, b, c = heapq.heappop(work)\n",
    "            res.append(c)\n",
    "            heapq.heappush(work, [v+a,b,c])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "\n",
    "        servers = [[s, i] for i, s in enumerate(servers)]\n",
    "        heapq.heapify(servers)\n",
    "\n",
    "        working = []\n",
    "        pending = Deque()\n",
    "\n",
    "        ret = [0] * len(tasks) \n",
    "\n",
    "        i = 0\n",
    "        while i < len(tasks) or pending:\n",
    "\n",
    "            if i < len(tasks):\n",
    "                pending.append((i, tasks[i]))\n",
    "\n",
    "            while working and working[0][0] == i:\n",
    "                heapq.heappush(servers, heapq.heappop(working)[1:])\n",
    "\n",
    "            while servers and pending:\n",
    "                task, time = pending.popleft()\n",
    "                s, idx = heapq.heappop(servers)\n",
    "                \n",
    "                ret[task] = idx\n",
    "                heapq.heappush(working, [i + time, s, idx])\n",
    "\n",
    "            if i < len(tasks):\n",
    "                i += 1\n",
    "            else:\n",
    "                i = working[0][0]\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        \n",
    "        q1=[[s,i,0] for i,s in enumerate(servers)]\n",
    "        q2=[]#t,s,i\n",
    "        heapq.heapify(q1)\n",
    "        ans=[]\n",
    "        for ti,task in enumerate(tasks):\n",
    "            while q2 and q2[0][0]<=ti or not q1:\n",
    "                t,s,i=heapq.heappop(q2)\n",
    "                heapq.heappush(q1,[s,i,t])\n",
    "           \n",
    "            s,i,t=heapq.heappop(q1)\n",
    "            heapq.heappush(q2,[max(t,ti)+task,s,i])\n",
    "            ans.append(i)\n",
    "          #  print('q1',q1)\n",
    "          #  print('q2',q2)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        servers_indices = [(server_wt, idx) for idx, server_wt in enumerate(servers)]\n",
    "        free_server_pq = []\n",
    "        heapq.heapify(free_server_pq)\n",
    "        for (server_wt, idx) in servers_indices:\n",
    "            heapq.heappush(free_server_pq, (server_wt, idx))\n",
    "        \n",
    "        # have another pq of working server which keep track f\n",
    "        working_server_pq = []\n",
    "        heapq.heapify(working_server_pq)\n",
    "\n",
    "        curr_time = 0\n",
    "        n = len(tasks)\n",
    "        res = [-1] * n\n",
    "        for i in range(n):\n",
    "            while working_server_pq and working_server_pq[0][0] <= i:\n",
    "                working_end, server_idx = heapq.heappop(working_server_pq)\n",
    "                heapq.heappush(free_server_pq, (servers[server_idx], server_idx))\n",
    "            # we need to assign a server to this task\n",
    "            if not free_server_pq:\n",
    "                # time jumps to where the first few servers are available\n",
    "                curr_time = working_server_pq[0][0]\n",
    "                while working_server_pq and working_server_pq[0][0] == curr_time:\n",
    "                    server_end, server_idx = heapq.heappop(working_server_pq)\n",
    "                \n",
    "                    heapq.heappush(free_server_pq, (servers[server_idx], server_idx))\n",
    "            curr_time = max(curr_time, i)\n",
    "            server_wt, server_idx = heapq.heappop(free_server_pq)\n",
    "            res[i] = server_idx\n",
    "            heapq.heappush(working_server_pq, (curr_time + tasks[i], server_idx))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:\n",
    "        servers_indices = [(server_wt, idx) for idx, server_wt in enumerate(servers)]\n",
    "        free_server_pq = []\n",
    "        heapq.heapify(free_server_pq)\n",
    "        for (server_wt, idx) in servers_indices:\n",
    "            heapq.heappush(free_server_pq, (server_wt, idx))\n",
    "        \n",
    "        # have another pq of working server which keep track f\n",
    "        working_server_pq = []\n",
    "        heapq.heapify(working_server_pq)\n",
    "\n",
    "        curr_time = 0\n",
    "        n = len(tasks)\n",
    "        res = [-1] * n\n",
    "        for i in range(n):\n",
    "            while working_server_pq and working_server_pq[0][0] <= i:\n",
    "                working_end, server_idx = heapq.heappop(working_server_pq)\n",
    "                heapq.heappush(free_server_pq, (servers[server_idx], server_idx))\n",
    "            # we need to assign a server to this task\n",
    "            if not free_server_pq:\n",
    "                # time jumps to where the first few servers are available\n",
    "                curr_time = working_server_pq[0][0]\n",
    "                while working_server_pq and working_server_pq[0][0] == curr_time:\n",
    "                    server_end, server_idx = heapq.heappop(working_server_pq)\n",
    "                \n",
    "                    heapq.heappush(free_server_pq, (servers[server_idx], server_idx))\n",
    "            curr_time = max(curr_time, i)\n",
    "            server_wt, server_idx = heapq.heappop(free_server_pq)\n",
    "            res[i] = server_idx\n",
    "            heapq.heappush(working_server_pq, (curr_time + tasks[i], server_idx))\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
